package leetcode.code0449;

import java.util.LinkedList;
import java.util.Queue;

import leetcode.helper.tree.TreeNode;

public class CodecError {
	public String serialize(TreeNode root) {
		if (root == null) {
			return null;
		}
		StringBuffer ans = new StringBuffer();
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(root);
		boolean hasNode = true;
		while (!queue.isEmpty() && hasNode) {
			int size = queue.size();
			hasNode = false;
			while (size > 0) {
				TreeNode node = queue.poll();
				if (node != null) {
					queue.add(node.left);
					queue.add(node.right);
					ans.append(node.val).append(",");
					if (node.left != null) {
						hasNode = true;
					}
					if (node.right != null) {
						hasNode = true;
					}
				} else {
					queue.add(null);
					queue.add(null);
					ans.append("null").append(",");
				}
				size--;
			}

		}
		return ans.substring(0, ans.length() - 1);
	}

	// Decodes your encoded data to tree.
	public TreeNode deserialize(String data) {
		if (data == null) {
			return null;
		}
		String[] vals = data.split(",");
		int len = vals.length;
		TreeNode root = new TreeNode(Integer.valueOf(vals[0]));
		int size = 1;
		int p = 1;
		Queue<TreeNode> list = new LinkedList<>();
		list.add(root);
		while (p < len) {
			size = list.size();
			int cnt = 0;
			while (cnt < size) {
				TreeNode node = list.poll();
				TreeNode node1 = null;
				TreeNode node2 = null;
				if (node != null) {
					String left = vals[p];
					String right = vals[p + 1];
					if (!left.equals("null")) {
						node1 = new TreeNode(Integer.valueOf(left));
					}
					if (!right.equals("null")) {
						node2 = new TreeNode(Integer.valueOf(right));
					}
				}
				node.left = node1;
				node.right = node2;
				list.add(node1);
				list.add(node2);
				p += 2;
				cnt++;
			}
		}
		return root;
	}
}
